package medium

import (
	. "GoLeetcode/common"
)

/*数学法：贝组定律

ax+by=z(a可以为正数也可以为负数) 有解当且仅当z是x，y最大公约数的倍数
注意：这里最多能装x+y的水，所以z必须<=x+y才有可能通过x，y构成z

当x,y的最大公约数为g时，x y可以构成[1, (x+y)/g]区间中的任意整数k*g

时间复杂度：O(log(min(x,y)))
空间复杂度：O(1)

*/
func canMeasureWater(x int, y int, z int) bool {
	if x == 0 || y == 0 {
		return z == x || z == y
	}
	g := GCD(x, y)
	return z <= x+y && z%g == 0
}

/*dfs
时间复杂度：O(xy) x桶最多有x+1种状态，y桶最多y+1种状态，所以一共有(x+1)(y+1)种状态
空间复杂度：O(xy) hash种最多存储(x+1)(y+1)种状态

*/

func canMeasureWater1(x int, y int, z int) bool {
	hash := make(map[[2]int]bool)
	var dfs func(xCur, yCur int) bool
	dfs = func(xCur, yCur int) bool {
		// 1.当x桶能构成z或y桶能构成z或x和y桶水量加起来能构成z，则可以
		if xCur == z || yCur == z || xCur+yCur == z {
			return true
		}
		// 2.判断当前状态是否之前遇到过，遇到过则返回，避免无限递归
		if _, ok := hash[[2]int{xCur, yCur}]; ok {
			return false
		}
		hash[[2]int{xCur, yCur}] = true

		// 3.状态变化:
		// 3.1 装满x桶或者装满y桶
		// 3.2 清空x桶或清空y桶
		// 3.3 用x桶的水装入y桶直到x桶没水或y桶装满 或 用y桶的水装入x桶直到y桶没水或x桶装满
		return dfs(x, yCur) || dfs(xCur, y) ||
			dfs(0, yCur) || dfs(xCur, 0) ||
			dfs(xCur-Min(xCur, y-yCur), yCur+Min(xCur, y-yCur)) || dfs(xCur+Min(yCur, x-xCur), yCur-Min(yCur, x-xCur))
	}
	return dfs(x, y)
}
